{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Longest Duplicate Substring"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #binary-search #suffix-array #sliding-window #hash-function #rolling-hash"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #二分查找 #后缀数组 #滑动窗口 #哈希函数 #滚动哈希"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: longestDupSubstring"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最长重复子串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串 <code>s</code> ，考虑其所有 <em>重复子串</em> ：即&nbsp;<code>s</code> 的（连续）子串，在 <code>s</code> 中出现 2 次或更多次。这些出现之间可能存在重叠。</p>\n",
    "\n",
    "<p>返回 <strong>任意一个</strong> 可能具有最长长度的重复子串。如果 <code>s</code> 不含重复子串，那么答案为 <code>\"\"</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"banana\"\n",
    "<strong>输出：</strong>\"ana\"\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"abcd\"\n",
    "<strong>输出：</strong>\"\"\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= s.length &lt;= 3 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>s</code> 由小写英文字母组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [longest-duplicate-substring](https://leetcode.cn/problems/longest-duplicate-substring/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [longest-duplicate-substring](https://leetcode.cn/problems/longest-duplicate-substring/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"banana\"', '\"abcd\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDupSubstring(self, s: str) -> str:\n",
    "        ret = \"\"\n",
    "        for i in range(len(s)):\n",
    "            w = len(ret) + 1\n",
    "            while s[i : i + w] in s[i + 1 :]:\n",
    "                ret = s[i : i + w]\n",
    "                w += 1\n",
    "                # print(f\"{i}, {w}, {ret}\")\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDupSubstring(self, s: str) -> str:\n",
    "        p = 13131\n",
    "        mod = 10 ** 18 + 7\n",
    "        suf = [0] * (len(s) + 1)\n",
    "        for i, c in enumerate(s):\n",
    "            x = ord(c)\n",
    "            suf[i + 1] = (suf[i] * p + x) % mod\n",
    "\n",
    "        def check(n: int) -> int:\n",
    "            vis = set()\n",
    "            for i in range(n, len(s) + 1):\n",
    "                x = (suf[i] - suf[i - n] * pow(p, n, mod)) % mod\n",
    "                if x in vis:\n",
    "                    return i - n\n",
    "                vis.add(x)\n",
    "            return -1\n",
    "        \n",
    "        left = 1\n",
    "        right = len(s) + 1\n",
    "        ans = ''\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            i = check(mid)\n",
    "            if i != -1:\n",
    "                ans = s[i: i + mid]\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDupSubstring(self, s: str) -> str:\n",
    "        # 生成两个进制\n",
    "        a1, a2 = random.randint(26, 100), random.randint(26, 100)\n",
    "        # 生成两个模\n",
    "        mod1, mod2 = random.randint(10**9+7, 2**31-1), random.randint(10**9+7, 2**31-1)\n",
    "        n = len(s)\n",
    "        # 先对所有字符进行编码\n",
    "        arr = [ord(c)-ord('a') for c in s]\n",
    "        # 二分查找的范围是[1, n-1]\n",
    "        l, r = 1, n-1\n",
    "        length, start = 0, -1\n",
    "        while l <= r:\n",
    "            m = l + (r - l + 1) // 2\n",
    "            idx = self.check(arr, m, a1, a2, mod1, mod2)\n",
    "            # 有重复子串，移动左边界\n",
    "            if idx != -1:\n",
    "                l = m + 1\n",
    "                length = m\n",
    "                start = idx\n",
    "            # 无重复子串，移动右边界\n",
    "            else:\n",
    "                r = m - 1\n",
    "        return s[start:start+length] if start != -1 else \"\"\n",
    "\n",
    "    def check(self, arr, m, a1, a2, mod1, mod2):\n",
    "        n = len(arr)\n",
    "        aL1, aL2 = pow(a1, m, mod1), pow(a2, m, mod2)\n",
    "        h1, h2 = 0, 0\n",
    "        for i in range(m):\n",
    "            h1 = (h1 * a1 + arr[i]) % mod1\n",
    "            h2 = (h2 * a2 + arr[i]) % mod2\n",
    "        # 存储一个编码组合是否出现过\n",
    "        seen = {(h1, h2)}\n",
    "        for start in range(1, n - m + 1):\n",
    "            h1 = (h1 * a1 - arr[start - 1] * aL1 + arr[start + m - 1]) % mod1\n",
    "            h2 = (h2 * a2 - arr[start - 1] * aL2 + arr[start + m - 1]) % mod2\n",
    "            # 如果重复，则返回重复串的起点\n",
    "            if (h1, h2) in seen:\n",
    "                return start\n",
    "            seen.add((h1, h2))\n",
    "        # 没有重复，则返回-1\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.a1 = 31\n",
    "        self.a2 = 71\n",
    "        self.MOD1 = 10 ** 9 + 7\n",
    "        self.MOD2 = 10 ** 9 + 9\n",
    "        self.encode = {chr(ord('a') + i): i for i in range(26)}\n",
    "        self.pow1 = []\n",
    "        self.pow2 = []\n",
    "\n",
    "    def longestDupSubstring(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        self.pow1 = [1] * n\n",
    "        self.pow2 = [1] * n\n",
    "        for i in range(1, n):\n",
    "            self.pow1[i] = self.pow1[i-1] * self.a1 % self.MOD1\n",
    "            self.pow2[i] = self.pow2[i-1] * self.a2 % self.MOD2\n",
    "            \n",
    "        left, right = 0, len(s)\n",
    "        start, length = 0, 0\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            idx = self.same_long_substr(s, mid)\n",
    "            if idx == -1:\n",
    "                right = mid\n",
    "            else:\n",
    "                start = idx\n",
    "                length = mid\n",
    "                left = mid + 1\n",
    "        return s[start: start+length] if length > 0 else \"\" \n",
    "    \n",
    "    def same_long_substr(self, s, length):\n",
    "        seen = set()\n",
    "        r1, r2 = self.pow1[length-1], self.pow2[length-1]\n",
    "        hash1 = 0\n",
    "        hash2 = 0\n",
    "        left, right = 0, 0\n",
    "        while right < len(s):\n",
    "            hash1 = (hash1 * self.a1 + self.encode[s[right]]) % self.MOD1\n",
    "            hash2 = (hash2 * self.a2 + self.encode[s[right]]) % self.MOD2\n",
    "            right += 1\n",
    "            if right - left == length:\n",
    "                if (hash1, hash2) in seen:\n",
    "                    return left\n",
    "                else:\n",
    "                    seen.add((hash1, hash2))\n",
    "                hash1 = (hash1 - self.encode[s[left]] * r1 + self.MOD1) % self.MOD1\n",
    "                hash2 = (hash2 - self.encode[s[left]] * r2 + self.MOD2) % self.MOD2\n",
    "                left += 1\n",
    "        return -1\n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class StringHash:\n",
    "    def __init__(self, s, b, m):\n",
    "        self.m = m\n",
    "        self.h = [0]\n",
    "        self.p = [1]\n",
    "        for c in s:\n",
    "            self.h.append((self.h[-1] * b + ord(c)) % m)\n",
    "            self.p.append((self.p[-1] * b) % m)\n",
    "\n",
    "    def hash(self, i, l):\n",
    "        return (self.h[i + l] - self.h[i] * self.p[l] + self.m) % self.m\n",
    "\n",
    "class Solution:\n",
    "    def longestDupSubstring(self, s: str) -> str:\n",
    "        def valid(cur_len):\n",
    "            seen = set()\n",
    "            for i in range(n - cur_len + 1):\n",
    "                v1, v2 = sh1.hash(i, cur_len), sh2.hash(i, cur_len)\n",
    "                if (v1, v2) in seen:\n",
    "                    return i\n",
    "                seen.add((v1, v2))\n",
    "            return -1\n",
    "\n",
    "        n = len(s)\n",
    "        l, r = 0, n\n",
    "        sh1 = StringHash(s, 1313, 10 ** 9 + 7)\n",
    "        sh2 = StringHash(s, 13131, 10 ** 9 + 9)\n",
    "        while l < r:\n",
    "            mid = l + (r - l + 1) // 2\n",
    "            idx = valid(mid)\n",
    "            if idx > -1:\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        idx = valid(l)\n",
    "        return s[idx:idx+l]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDupSubstring(self, s: str) -> str:\n",
    "        posrecord = collections.defaultdict(list)\n",
    "        for i, ch in enumerate(s):\n",
    "            posrecord[ch].append(i)\n",
    "        left, right = 1, len(s)\n",
    "        length = 0\n",
    "        result = -1\n",
    "        while left < right and right > length:\n",
    "            mid = (left + right) // 2\n",
    "            valid, start = self.check(s, posrecord, mid)\n",
    "            if not valid:\n",
    "                right = mid \n",
    "            else:\n",
    "                left = mid + 1 \n",
    "                result = start\n",
    "                length = mid\n",
    "        \n",
    "        if result == -1:\n",
    "            return ''\n",
    "        return s[result:result + length]\n",
    "\n",
    "    def check(self, s, posrecord, length):\n",
    "        for ch in posrecord:\n",
    "            if len(posrecord[ch]) > 1:\n",
    "                record = set()\n",
    "                for i in range(len(posrecord[ch])):\n",
    "                    start = posrecord[ch][i]\n",
    "                    end = min(len(s), posrecord[ch][i] + length)\n",
    "                    if s[start:end] in record:\n",
    "                        return True, start\n",
    "                    record.add(s[start:end])\n",
    "        return False, 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import islice\n",
    "\n",
    "class Solution:\n",
    "    def longestDupSubstring(self, S: str) -> str:\n",
    "        rank_to_index = list(range(len(S)))\n",
    "        index_to_rank = [0] * len(S)\n",
    "        index_to_rank2 = [0] * len(S)\n",
    "        for i, a in enumerate(S):\n",
    "            index_to_rank[i] = ord(a)\n",
    "        rank_to_index.sort(key=lambda x: index_to_rank[x])\n",
    "        l = 1\n",
    "        def next_rank(x):\n",
    "            return (index_to_rank[x], index_to_rank[x + l] if x + l < len(S) else -1)\n",
    "        while l < len(S):\n",
    "            rank_to_index.sort(key=next_rank)\n",
    "            r = 0\n",
    "            index_to_rank2[rank_to_index[0]] = r\n",
    "            lr = next_rank(rank_to_index[0])\n",
    "            for ind in islice(rank_to_index, 1, None):\n",
    "                nr = next_rank(ind)\n",
    "                if nr != lr:\n",
    "                    r += 1\n",
    "                    lr = nr\n",
    "                index_to_rank2[ind] = r\n",
    "            index_to_rank, index_to_rank2 = index_to_rank2, index_to_rank\n",
    "            l += l\n",
    "            if r == len(index_to_rank):\n",
    "                break\n",
    "        ans = 0\n",
    "        pos = 0\n",
    "        H = 1\n",
    "        for i in range(len(S)):\n",
    "            if len(S) - i < ans:\n",
    "                break\n",
    "            r = index_to_rank[i]\n",
    "            if r > 0:\n",
    "                j = rank_to_index[r - 1]\n",
    "                if H > 0:\n",
    "                    H -= 1\n",
    "                while i + H < len(S) and j + H < len(S) and S[i + H] == S[j + H]:\n",
    "                    H += 1\n",
    "                if H > ans:\n",
    "                    ans = H\n",
    "                    pos = i\n",
    "            else:\n",
    "                H = 0\n",
    "        return S[pos: pos + ans]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDupSubstring(self, s: str) -> str:\n",
    "        k=512\n",
    "        n=len(s)\n",
    "        m=max(27,n+1)\n",
    "        idx=list(range(n))\n",
    "        idx.sort(key=lambda i:s[i:i+k])\n",
    "        rk=[0]*n\n",
    "        cnt=[0]*m \n",
    "        ri=1\n",
    "        rk[idx[0]]=ri \n",
    "        for i in range(1,n):\n",
    "            if s[idx[i]:idx[i]+k]!=s[idx[i-1]:idx[i-1]+k]:\n",
    "                # cnt[ri]=i \n",
    "                ri+=1\n",
    "            rk[idx[i]]=ri\n",
    "        # cnt[ri]=n \n",
    "        k=1\n",
    "        rk2=[0]*n \n",
    "        while k<n:\n",
    "            # print(rk)\n",
    "            idx.sort(key=lambda i:(rk[i],rk[i+k] if i+k<n else 0))\n",
    "            ri=1\n",
    "            rk2[idx[0]]=ri\n",
    "            for i in range(1,n):\n",
    "                i1=idx[i]\n",
    "                i2=idx[i-1]\n",
    "                if rk[i1]!=rk[i2] or (rk[i1+k] if i1+k<n else 0)!=(rk[i2+k] if i2+k<n else 0):\n",
    "                    # cnt[ri]=i \n",
    "                    ri+=1 \n",
    "                rk2[i1]=ri\n",
    "                # print(i1,ri)\n",
    "            # cnt[ri]=n \n",
    "            rk,rk2=rk2,rk\n",
    "            k<<=1\n",
    "        t=0\n",
    "        ans=\"\"\n",
    "        for i in range(n):\n",
    "            rk[idx[i]]=i \n",
    "        for i in range(n):\n",
    "            if rk[i]==0:\n",
    "                continue \n",
    "            if t>0:\n",
    "                t-=1\n",
    "            j=idx[rk[i]-1]\n",
    "            # if s[i]=='h':\n",
    "            #     print(s[i:i+5],s[j:j+5])\n",
    "            while j+t<n and i+t<n and s[i+t]==s[j+t]:\n",
    "                t+=1\n",
    "            if t>len(ans):\n",
    "                ans=s[i:i+t]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:    \n",
    "    def longestDupSubstring(self, S):\n",
    "        beg, end = 0, len(S)\n",
    "        q = (1<<31) - 1 \n",
    "        Found = \"\"\n",
    "        while beg + 1 < end:\n",
    "            mid = (beg + end)//2\n",
    "            isFound, candidate = self.RabinKarp(S, mid, q)\n",
    "            if isFound:\n",
    "                beg, Found = mid, candidate\n",
    "            else:\n",
    "                end = mid\n",
    "        return Found\n",
    " \n",
    "    def RabinKarp(self,text, M, q):\n",
    "        if M == 0: \n",
    "            return True\n",
    "        h, t, d = (1 << (8*M-8)) % q, 0, 256\n",
    "        dic = defaultdict(list)\n",
    "        for i in range(M): \n",
    "            t = (d * t + ord(text[i])) % q\n",
    "        dic[t].append(i - M + 1)\n",
    "        for i in range(len(text) - M):\n",
    "            t = (d * (t-ord(text[i]) * h) + ord(text[i + M]))% q\n",
    "            for j in dic[t]:\n",
    "                if text[i+1 : i+M+1] == text[j : j+M]:\n",
    "                    return (True, text[j : j+M])\n",
    "            dic[t].append(i + 1)\n",
    "        return (False, \"\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import sys\n",
    "sys.setrecursionlimit(3000000)\n",
    "class Solution:\n",
    "    def longestDupSubstring(self, s: str) -> str:\n",
    "        nums = [ord(c)-ord('a') for c in s]\n",
    "        #print(len(s))\n",
    "        mod = 10**9+7\n",
    "\n",
    "        @cache\n",
    "        def gettimes(k):\n",
    "            #26**k\n",
    "            if k==0:\n",
    "                return 1\n",
    "            return (26*gettimes(k-1))%mod\n",
    "        def issame(idx1,idx2,lenth):\n",
    "            #print(idx1,idx2,lenth)\n",
    "            for i in range(lenth):\n",
    "                if s[idx1+i]!=s[idx2+i]:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        def getsubstr(lenth):\n",
    "            maps={}\n",
    "            tmpval = 0\n",
    "            for i in range(lenth):\n",
    "                tmpval *= 26\n",
    "                tmpval += nums[i]\n",
    "                tmpval %= mod\n",
    "            idx = 0\n",
    "            maps[tmpval]=[idx]\n",
    "            while idx+lenth<len(nums):\n",
    "                tmpval -= nums[idx]*gettimes(lenth-1)\n",
    "                tmpval *= 26\n",
    "                tmpval += nums[idx+lenth]\n",
    "                tmpval %= mod\n",
    "                idx += 1\n",
    "                if tmpval in maps:\n",
    "                    for preidx in maps[tmpval]:\n",
    "                        if issame(preidx,idx,lenth):\n",
    "                            return [preidx,lenth]\n",
    "                    maps[tmpval].append(idx)\n",
    "                else:\n",
    "                    maps[tmpval]=[idx]\n",
    "            return []\n",
    "        left = 1\n",
    "        right = len(s)-1\n",
    "        ans = ''\n",
    "        while right>=left:\n",
    "            mid = (right+left)//2\n",
    "            tmp = getsubstr(mid)\n",
    "            if len(tmp)>0:\n",
    "                ans = s[tmp[0]:tmp[0]+tmp[1]]\n",
    "                left = mid+1\n",
    "            else:\n",
    "                right = mid-1\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from enum import Enum\n",
    "from typing import Optional\n",
    "import string\n",
    "# from suffix_tree_ukkonen_example_viz import visualize_tree, visualize_graphviz\n",
    "\n",
    "\n",
    "class Path:\n",
    "    def __init__(self, path_start: int = -1, path_end: int = -1):\n",
    "        # assert path_end >= path_start\n",
    "        self._path_start = path_start\n",
    "        self._path_end = path_end\n",
    "\n",
    "    def get_path_start(self):\n",
    "        # assert 0 <= self._path_start <= self._path_end\n",
    "        return self._path_start\n",
    "\n",
    "    def get_path_end(self):\n",
    "        # assert 0 <= self._path_start <= self._path_end\n",
    "        return self._path_end\n",
    "\n",
    "    def set_path_start(self, path_start: int):\n",
    "        # assert path_start >= 0\n",
    "        self._path_start = path_start\n",
    "\n",
    "    def set_path_end(self, path_end: int):\n",
    "        # assert path_end >= 0\n",
    "        self._path_end = path_end\n",
    "\n",
    "    def __len__(self):\n",
    "        if self._path_start == -1 and self._path_end == -1:\n",
    "            return 0\n",
    "        else:\n",
    "            return self._path_end - self._path_start + 1\n",
    "\n",
    "    def clear(self):\n",
    "        self._path_start = -1\n",
    "        self._path_end = -1\n",
    "\n",
    "    def print_path(self, txt: str):\n",
    "        if self._path_start == -1 and self._path_end == -1:\n",
    "            print(\"Path: <empty>\")\n",
    "        else:\n",
    "            # print(self._path_start)\n",
    "            # print(self._path_end)\n",
    "            print(\"Path: \", txt[self._path_start:self._path_end+1])\n",
    "\n",
    "\n",
    "class NodeType(Enum):\n",
    "    ROOT = 1        # root\n",
    "    INODE = 2       # internal node\n",
    "    LEAF = 3        # leaf\n",
    "\n",
    "\n",
    "class Node:\n",
    "    global_root = None\n",
    "    global_end = None\n",
    "\n",
    "    def __init__(self, node_type: NodeType, start_index: int = -1, end_index: int = -1):\n",
    "        if node_type != NodeType.ROOT:\n",
    "            assert self.global_root is not None, \"please initialize the global root....\"\n",
    "        # the required attributes for a node\n",
    "        self._start_index = start_index\n",
    "        self._end_index = end_index\n",
    "        self._children = {}\n",
    "        # other attributes\n",
    "        self._node_type = node_type\n",
    "        # the leaf id\n",
    "        self._leaf_id = -1\n",
    "        # total path length until this node\n",
    "        self._total_len = -1\n",
    "        # parent of the node\n",
    "        self._parent = None\n",
    "\n",
    "        # initialize the suffix link\n",
    "        if node_type == NodeType.ROOT:\n",
    "            # if this node will be a root, suffix link to itself\n",
    "            self.suffix_link = self\n",
    "        else:\n",
    "            # every node will go back to root for now...\n",
    "            self.suffix_link = self.global_root\n",
    "\n",
    "    def set_parent_node(self, pn):\n",
    "        self._parent = pn\n",
    "\n",
    "    def get_parent_node(self):\n",
    "        assert self._parent is not None\n",
    "        return self._parent\n",
    "\n",
    "    def get_total_len(self):\n",
    "        if self._node_type == NodeType.ROOT:\n",
    "            return 0\n",
    "        else:\n",
    "            # assert self._total_len >= 0, \"Only internal nodes can have the total length....\"\n",
    "            return self._total_len\n",
    "\n",
    "    def set_total_len(self, total_len: int):\n",
    "        # assert self._node_type == NodeType.INODE\n",
    "        # assert total_len >= 0\n",
    "        self._total_len = total_len\n",
    "\n",
    "    def get_node_type(self):\n",
    "        return self._node_type\n",
    "\n",
    "    def set_leaf_id(self, j: int):\n",
    "        # assert self._node_type == NodeType.LEAF, \"only leaf has leaf id to express a suffix...\"\n",
    "        # assert j >= 0, \"the suffix should start from 0 to n-1\"\n",
    "        # the j th suffixes in the text string... .\n",
    "        self._leaf_id = j\n",
    "\n",
    "    def get_leaf_id(self) -> int:\n",
    "        # assert self._node_type == NodeType.LEAF, \"only leaf has leaf id to express a suffix...\"\n",
    "        # assert self._leaf_id >= 0, \"you should initialize the leaf if of a leaf....\"\n",
    "        return self._leaf_id\n",
    "\n",
    "    def set_start_index(self, start_index: int):\n",
    "        # assert self._node_type != NodeType.ROOT, \"the root does not have incoming edges....\"\n",
    "        # assert start_index >= 0, \"the starting index should be integers in  [0, n)\"\n",
    "        self._start_index = start_index\n",
    "\n",
    "    def get_start_index(self) -> int:\n",
    "        # assert self._node_type != NodeType.ROOT, \"the root does not have incoming edges....\"\n",
    "        # assert self._start_index >= 0, \"you must initialise the starting index of edge.....\"\n",
    "        return self._start_index\n",
    "\n",
    "    def set_end_index(self, end_index: int):\n",
    "        # root does not have edge, and leaf has a global end....\n",
    "        # assert self._node_type == NodeType.INODE, \"only internal nodes have ending index of edge....\"\n",
    "        # assert end_index >= 0 and self._start_index <= end_index, \"the ending index should be integers in  [0, n)\"\n",
    "        self._end_index = end_index\n",
    "\n",
    "    def get_end_index(self) -> int:\n",
    "        if self._node_type == NodeType.LEAF:\n",
    "            # assert self.global_end is not None\n",
    "            return self.global_end\n",
    "        elif self._node_type == NodeType.INODE:\n",
    "            # assert self._end_index >= 0, \"you must initialise the ending index of edge.....\"\n",
    "            return self._end_index\n",
    "        else:\n",
    "            raise AssertionError(\"the node should have a type....\")\n",
    "\n",
    "    def add_child_node(self, child_edge_start_char: str, child_node):\n",
    "        # assert self._node_type != NodeType.LEAF, \"leaf should not have any outgoing edges....\"\n",
    "        # assert child_node._start_index >= 0, \"you should initialize the first edge of the child...\"\n",
    "        # add the child to the set of outgoing edges from this node.\n",
    "        self._children[child_edge_start_char] = child_node\n",
    "\n",
    "    def __len__(self):\n",
    "        if self._node_type == NodeType.LEAF:\n",
    "            # assert self._start_index >= 0, \"remember to initialize the starting index of the leaf...\"\n",
    "            # assert self.global_end is not None, \"remember to give the text as a global end\"\n",
    "            # assert self.global_end >= self._start_index, \"forget to update the global end ? Rule 1? \"\n",
    "            # to implement an online ukkonen, the global_end has to be a variable that is increased in each iteration.\n",
    "            return self.global_end - self._start_index + 1\n",
    "\n",
    "        elif self._node_type == NodeType.ROOT:\n",
    "            return 0\n",
    "\n",
    "        else:\n",
    "            # assert self._start_index >= 0, \"remember to initialize the starting index of the internal node...\"\n",
    "            # assert self._end_index >= 0, \"remember to initialize the ending index of the internal node...\"\n",
    "            # assert self._start_index <= self._end_index\n",
    "            return self._end_index - self._start_index + 1\n",
    "\n",
    "    def get_child(self, child_edge_start_char: str):\n",
    "        # assert len(child_edge_start_char) == 1\n",
    "        # assert child_edge_start_char in self._children\n",
    "        return self._children[child_edge_start_char]\n",
    "\n",
    "    def has_child(self, child_edge_start_char: str) -> bool:\n",
    "        return child_edge_start_char in self._children\n",
    "\n",
    "    def get_all_children(self):\n",
    "        return self._children\n",
    "\n",
    "    def get_children_size(self) -> int:\n",
    "        return len(self._children)\n",
    "\n",
    "    def set_suffix_link(self, v):\n",
    "        self.suffix_link = v\n",
    "\n",
    "\n",
    "class SuffixTree:\n",
    "    def __init__(self, txt: str):\n",
    "        self.ans = \"\"\n",
    "\n",
    "        assert len(txt) > 0, \"non-empty string....\"\n",
    "\n",
    "        # to build a explicit suffix tree....\n",
    "        self.txt = txt + '\\0'\n",
    "\n",
    "        # create the root for the suffix tree\n",
    "        self.root = Node(NodeType.ROOT)\n",
    "        self.root.set_parent_node(self.root)    # note that root's parent is also itself.\n",
    "        # initialize some variables....\n",
    "        self.last_j = -1\n",
    "        Node.global_root = self.root            # all nodes should know which is the root.\n",
    "\n",
    "        # an internal node that is waiting for the suffix link connection ....\n",
    "        self.pending_suffix_link: Optional[Node] = None\n",
    "\n",
    "        # a list of leaves\n",
    "        self.leaves_list = []\n",
    "\n",
    "        # ukkonen construction.....\n",
    "        self.ukkonen()\n",
    "        # visualize_graphviz(self)\n",
    "\n",
    "    def ukkonen(self):\n",
    "        # ----------------------------------------------------------------\n",
    "        # Base Case : O(1)\n",
    "        full_suffix_leaf = Node(NodeType.LEAF)\n",
    "        full_suffix_leaf.set_leaf_id(0)\n",
    "        self.leaves_list.append(full_suffix_leaf)\n",
    "        # start and end of the full suffix...\n",
    "        full_suffix_leaf.set_start_index(0)\n",
    "        Node.global_end = 0\n",
    "\n",
    "        # add the leaf to the root (and set leaf's parent as root)\n",
    "        self.root.add_child_node(self.txt[0], full_suffix_leaf)\n",
    "        full_suffix_leaf.set_parent_node(self.root)\n",
    "\n",
    "        # ----------------------------------------------------------------\n",
    "        # Initialise variables, active node, remainder, last_j and global_end\n",
    "        active_node = self.root\n",
    "        remainder = Path()\n",
    "        self.last_j = 0\n",
    "\n",
    "        for i in range(1, len(self.txt)):\n",
    "            Node.global_end += 1\n",
    "            for j in range(self.last_j+1, i+1):\n",
    "                # print(i)\n",
    "                # print(\"-\", j, i)\n",
    "                # print(\"-\", self.txt[j:i])\n",
    "                # print(\"-\", self.txt[i])\n",
    "                # print(\"....................\")\n",
    "                # ----------------------------------------------------------------\n",
    "                # update the active node and remainder by traversing down the tree....\n",
    "                if j == i:\n",
    "                    # insert a new leaf to the root....\n",
    "                    active_node = self.root\n",
    "                    remainder.clear()\n",
    "                else:\n",
    "                    # active_node, remainder = self.traverse_down(self.root, Path(j, i-1))\n",
    "                    active_node, remainder = self._traverse_down(active_node, remainder)\n",
    "\n",
    "                # ----------------------------------------------------------------\n",
    "                # apply the appropriate extension txt[i]\n",
    "                if self._make_extension(j, i, active_node, remainder) == 3:\n",
    "                    # print(\"RULE 3\")\n",
    "                    # 1. resolve any pending suffix links from the previous extension\n",
    "                    if self.pending_suffix_link is not None:\n",
    "                        self.pending_suffix_link.set_suffix_link(active_node)\n",
    "                        self.pending_suffix_link = None\n",
    "\n",
    "                    # 2. prepare to move to next phase (lecture note book, pp57 Rule 3 extensions in Ukkonen's)\n",
    "                    #    and update the remainder (but don't follow the suffix link)....\n",
    "                    if len(remainder) > 0:\n",
    "                        remainder.set_path_end(remainder.get_path_end() + 1)\n",
    "                    else:\n",
    "                        remainder.set_path_start(i)\n",
    "                        remainder.set_path_end(i)\n",
    "                    # remainder.print_path(self.txt)\n",
    "                    # 3. terminate this phase early i.e. showstopper\n",
    "                    break\n",
    "                else:\n",
    "                    # print(\"RULE 2\")\n",
    "                    # 1. resolve any pending suffix links from the previous extension\n",
    "                    #    (it has been resolved in the make_extension function....)\n",
    "\n",
    "                    # 2. follow the suffix link and update the active node and remainder...\n",
    "                    if active_node == self.root:\n",
    "                        # if u = r, then v = r, remove the first character from the remainder...\n",
    "                        if len(remainder) <= 1:\n",
    "                            remainder.clear()\n",
    "                        if len(remainder) > 1:\n",
    "                            remainder.set_path_start(remainder.get_path_start() + 1)\n",
    "                    else:\n",
    "                        # if u != r, u must be an internal node.\n",
    "                        # follow the suffix link and keep the remainder...\n",
    "                        active_node = active_node.suffix_link\n",
    "\n",
    "                    # print(j+1, i+1)\n",
    "                    # remainder.print_path(self.txt)\n",
    "\n",
    "                    # 3. move to next extension\n",
    "                    #   (i.e. traversing suffix links (lecture note book, pp49 General extension procedure)\n",
    "                # print(\"---------------------------------------------------------------------------------------------\")\n",
    "\n",
    "        # visualize_tree(self.root, self.txt)\n",
    "\n",
    "    def _traverse_down(self, acn: Node, rem: Path):\n",
    "        \"\"\"\n",
    "        This function essentially update the active node and remainder by the skip-count trick....\n",
    "        :param acn: active node\n",
    "        :param rem: remainder\n",
    "        :return:\n",
    "        \"\"\"\n",
    "\n",
    "        # if the given path is empty....\n",
    "        if len(rem) == 0:\n",
    "            rem.clear()\n",
    "            return acn, rem\n",
    "\n",
    "        # n is in fact the active node\n",
    "        remainder_len = len(rem)\n",
    "        start_idx = rem.get_path_start()\n",
    "        n_parent = acn\n",
    "        n = acn.get_child(self.txt[start_idx])\n",
    "\n",
    "        while remainder_len > 0:\n",
    "            if remainder_len < len(n):\n",
    "                break\n",
    "            if remainder_len == len(n):\n",
    "                rem.clear()\n",
    "                return n, rem\n",
    "            else:\n",
    "                start_idx += len(n)\n",
    "                remainder_len -= len(n)\n",
    "                n_parent = n\n",
    "                n = n.get_child(self.txt[start_idx])\n",
    "\n",
    "        # update the remainder....\n",
    "        rem.set_path_start(n.get_start_index())\n",
    "        rem.set_path_end(n.get_start_index() + remainder_len - 1)\n",
    "        return n_parent, rem\n",
    "\n",
    "    def _make_extension(self, j: int, i: int, active_node: Node, remainder: Path):\n",
    "        if len(remainder) == 0:\n",
    "            if not active_node.has_child(self.txt[i]):\n",
    "                # print(\"RULE 2 - only add a leaf\")\n",
    "                new_leaf = Node(NodeType.LEAF, i)\n",
    "                new_leaf.set_leaf_id(j)\n",
    "                # append the new leaf to the current active node and set new_leaf's parent as current active node\n",
    "                active_node.add_child_node(self.txt[i], new_leaf)\n",
    "                new_leaf.set_parent_node(active_node)\n",
    "                # add leaves to a static list, so easy to manage all leaves....\n",
    "                self.leaves_list.append(new_leaf)\n",
    "                self.last_j += 1\n",
    "\n",
    "                # the previous internal node that waiting for suffix link should connect the current active node.\n",
    "                if self.pending_suffix_link is not None:\n",
    "                    self.pending_suffix_link.set_suffix_link(active_node)\n",
    "                    self.pending_suffix_link = None\n",
    "                return 2\n",
    "            else:\n",
    "                # print(\"RULE 3\")\n",
    "                return 3\n",
    "\n",
    "        else:\n",
    "            if self.txt[i] == self.txt[remainder.get_path_end()+1]:\n",
    "                # print(\"RULE 3\")\n",
    "                return 3\n",
    "            else:\n",
    "                # print(\"RULE 2 - add a leaf and an internal node\")\n",
    "                new_internal_node = Node(NodeType.INODE, remainder.get_path_start(), remainder.get_path_end())\n",
    "\n",
    "                # the node under the new internal node (it starting edge index and parent change!!)\n",
    "                active_node.get_child(self.txt[remainder.get_path_start()]).set_start_index(remainder.get_path_end()+1)\n",
    "                active_node.get_child(self.txt[remainder.get_path_start()]).set_parent_node(new_internal_node)\n",
    "\n",
    "                # the new internal should take current active node's child, and internal node's parent as active node..\n",
    "                new_internal_node.add_child_node(self.txt[remainder.get_path_end()+1],\n",
    "                                                 active_node.get_child(self.txt[remainder.get_path_start()]))\n",
    "                new_internal_node.set_parent_node(active_node)\n",
    "\n",
    "                # only internal node has the total path length..... ()\n",
    "                new_internal_node.set_total_len(active_node.get_total_len() + len(remainder))\n",
    "                tmp = self.txt[j:i]\n",
    "                if len(tmp) > len(self.ans):\n",
    "                    self.ans = tmp\n",
    "\n",
    "                # create a new leaf because of rule 2\n",
    "                new_leaf = Node(NodeType.LEAF, i)\n",
    "                new_leaf.set_leaf_id(j)\n",
    "                # (append the new leaf to the new internal node, because of rule 2, and don't forget leaf's parent)....\n",
    "                new_internal_node.add_child_node(self.txt[i], new_leaf)\n",
    "                new_leaf.set_parent_node(new_internal_node)\n",
    "                # add leaves to a static list, so easy to manage all leaves....\n",
    "                self.leaves_list.append(new_leaf)\n",
    "\n",
    "                # update active node's child, which should be the new internal node....\n",
    "                active_node.add_child_node(self.txt[remainder.get_path_start()], new_internal_node)\n",
    "\n",
    "                # since rule 2 is applied, the last_j indicate the last rule 2 extension, so increase it.\n",
    "                self.last_j += 1\n",
    "\n",
    "                # the previous internal node that waiting for suffix link should connect this new internal node.\n",
    "                if self.pending_suffix_link is not None:\n",
    "                    self.pending_suffix_link.set_suffix_link(new_internal_node)\n",
    "                    self.pending_suffix_link = None\n",
    "\n",
    "                # now this new internal node is waiting for suffix link\n",
    "                self.pending_suffix_link = new_internal_node\n",
    "\n",
    "                return 2\n",
    "\n",
    "    def search_tree_traversal(self, q: str):\n",
    "        \"\"\"\n",
    "        Assume a tuple (node, k).\n",
    "        node is the current node,\n",
    "        k is the position of the edge label where comparison stops (substring)\n",
    "        Traverse the tree following the path given by the query string q.\n",
    "            - Case 1: If we fall off the tree, that means not a substring of suffix.\n",
    "            - Case 2a: If we stop at the middle of the edge, that means a substring.\n",
    "            - Case 2b: If we finish at a node, that means a true suffix.\n",
    "        :param q: the query string\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        curr_node = self.root\n",
    "        j = 0\n",
    "        while j < len(q):\n",
    "            c = q[j]\n",
    "            # Case 1: fell off the tree (fell off at node)\n",
    "            if not curr_node.has_child(c):\n",
    "                return None\n",
    "            else:\n",
    "                child = curr_node.get_child(c)\n",
    "                edge_label = self.txt[child.get_start_index():child.get_end_index()+1]\n",
    "                k = j + 1\n",
    "                while k < len(q) and k - j < len(edge_label) and q[k] == edge_label[k - j]:\n",
    "                    k += 1\n",
    "                # Next iteration: exhausted edge (shift to the next node and go further)\n",
    "                if k - j == len(edge_label):\n",
    "                    curr_node = child\n",
    "                    j = k\n",
    "                # can't dive deeper into the tree\n",
    "                # Case 2a : exhausted query string in middle of edge (substring)\n",
    "                elif k == len(q):\n",
    "                    curr_node = child\n",
    "                    if len(curr_node.get_all_children()) == 0:\n",
    "                        # print(\"substring\")\n",
    "                        # print(curr_node.leaf_id)\n",
    "                        pass\n",
    "                    return curr_node\n",
    "                # Case 1: fell off in the middle of edge (since q[k] != edge_label[k]) breaks..\n",
    "                else:\n",
    "                    return None\n",
    "\n",
    "        # Case 2b: exhausted query string at a node\n",
    "        #   (just next to a node, but don't fall off the tree).\n",
    "        return curr_node\n",
    "\n",
    "    @staticmethod\n",
    "    def dfs(n: Node):\n",
    "        \"\"\"\n",
    "        use the dfs for tree traversing from the node n\n",
    "        NOTE: the 'visited property' is not important in a tree (compared to graph).\n",
    "              (why? we can't go back. so don't need to mark the node as visited).\n",
    "        :param n: a node in the tree\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        # the full alphabet set....\n",
    "        alphabet_set = string.printable[::-1] + '\\0'\n",
    "\n",
    "        # the stack for DFS\n",
    "        stack = [n]\n",
    "        ans = []\n",
    "        while len(stack) > 0:\n",
    "            v = stack.pop()\n",
    "            if len(v.get_all_children()) == 0:\n",
    "                # at a leaf node (return the answer)\n",
    "                ans.append(v.get_leaf_id())\n",
    "            else:\n",
    "                for c in alphabet_set:\n",
    "                    if v.has_child(c):\n",
    "                        stack.append(v.get_child(c))\n",
    "\n",
    "        # ans.sort()  # sort is recommended to be done outside.\n",
    "        return ans\n",
    "\n",
    "    def search_substring(self, q: str):\n",
    "        # follow the path of the query string q, to the nearest next node.\n",
    "        node = self.search_tree_traversal(q)\n",
    "        if node is not None:\n",
    "            # traversal all leaves in a tree (https://en.wikipedia.org/wiki/Tree_traversal)\n",
    "            return self.dfs(node)\n",
    "        else:\n",
    "            return []\n",
    "\n",
    "\n",
    "# https://leetcode.com/problems/longest-duplicate-substring/discuss/312999/Best-Java-O(n)-complexity-and-O(n)-space-Solution-Suffix-Tree-67ms\n",
    "\n",
    "class Solution:\n",
    "    def longestDupSubstring(self, s: str) -> str:\n",
    "        return SuffixTree(s).ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def longestDupSubstring(self, s: str) -> str:\n",
    "        curResult2 = []\n",
    "        final_result = {}\n",
    "        # final_result2 = {}\n",
    "        max_string = ''\n",
    "        max_string_len = len(max_string)\n",
    "        half_max_len = len(s) >> 1\n",
    "        s_length = len(s)\n",
    "        if s_length == 2:\n",
    "            curResult2.append(s)\n",
    "            curResult2.append(s[0])\n",
    "            curResult2.append(s[1])\n",
    "            for result in curResult2:\n",
    "                if final_result.get(result) is not None and len(max_string) < len(result):\n",
    "                    max_string = result\n",
    "                else:\n",
    "                    final_result[result] = 1\n",
    "            return max_string\n",
    "        # elif s_length % 2 == 0:\n",
    "        #     half_s_length = s_length >> 1\n",
    "        #     if s[0:half_s_length] == s[half_s_length: s_length]:\n",
    "        #         return s[0:half_s_length]\n",
    "        else:\n",
    "            if s.count(s[0]) == len(s):\n",
    "                return s[0:len(s)-1]\n",
    "            half_s_length = s_length >> 1\n",
    "            if s_length % 2 == 0:\n",
    "                if s[0:half_s_length] == s[half_s_length: s_length]:\n",
    "                    return s[0:half_s_length]\n",
    "            else:\n",
    "                if s[0:half_s_length] == s[half_s_length+1: s_length]:\n",
    "                    return s[0:half_s_length]\n",
    "\n",
    "            start_index: int = 0\n",
    "            end_index: int = len(s)\n",
    "            curResult2.append(s[start_index])\n",
    "            start_index += 1\n",
    "            # changed_flag = False\n",
    "            while start_index < end_index:\n",
    "                tempResult = []\n",
    "                append_string = s[start_index: start_index + 1]\n",
    "                for x in curResult2:\n",
    "                    if final_result.get(x) is not None:\n",
    "                        if max_string_len < len(x):\n",
    "                            max_string = x\n",
    "                            max_string_len = len(x)\n",
    "                            # changed_flag = True\n",
    "                    else:\n",
    "                        final_result[x] = 0\n",
    "                    new_string = x + append_string\n",
    "                    if len(x) <=  max_string_len + 3:\n",
    "                        tempResult.append(new_string)\n",
    "                tempResult.append(append_string)\n",
    "                curResult2.clear()\n",
    "                curResult2 = tempResult\n",
    "                start_index += 1\n",
    "\n",
    "            for x in curResult2:\n",
    "                if final_result.get(x) is not None:\n",
    "                    if max_string_len < len(x):\n",
    "                        max_string = x\n",
    "                        max_string_len = len(x)\n",
    "                else:\n",
    "                    final_result[x] = 0\n",
    "\n",
    "            x = s.find(max_string)\n",
    "            y = s.find(max_string, x + len(max_string))\n",
    "            new_start1 = x + len(max_string)\n",
    "            new_start2 = y + len(max_string)\n",
    "            count: int = 0\n",
    "\n",
    "            while new_start1 < y:\n",
    "                x_char = s[new_start1:new_start1 + 1]\n",
    "                y_char = s[new_start2:new_start2 + 1]\n",
    "                if x_char == y_char:\n",
    "                    count += 1\n",
    "                else:\n",
    "                    break\n",
    "                new_start1 += 1\n",
    "                new_start2 += 1\n",
    "            return s[x:x + len(max_string) + count]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDupSubstring(self, s: str) -> str:\n",
    "        k=1024\n",
    "        n=len(s)\n",
    "        m=max(27,n+1)\n",
    "        idx=list(range(n))\n",
    "        idx.sort(key=lambda i:s[i:i+k])\n",
    "        rk=[0]*n\n",
    "        cnt=[0]*m \n",
    "        ri=1\n",
    "        rk[idx[0]]=ri \n",
    "        for i in range(1,n):\n",
    "            if s[idx[i]:idx[i]+k]!=s[idx[i-1]:idx[i-1]+k]:\n",
    "                # cnt[ri]=i \n",
    "                ri+=1\n",
    "            rk[idx[i]]=ri\n",
    "        # cnt[ri]=n \n",
    "        k=1\n",
    "        rk2=[0]*n \n",
    "        while k<n:\n",
    "            # print(rk)\n",
    "            idx.sort(key=lambda i:(rk[i],rk[i+k] if i+k<n else 0))\n",
    "            ri=1\n",
    "            rk2[idx[0]]=ri\n",
    "            for i in range(1,n):\n",
    "                i1=idx[i]\n",
    "                i2=idx[i-1]\n",
    "                if rk[i1]!=rk[i2] or (rk[i1+k] if i1+k<n else 0)!=(rk[i2+k] if i2+k<n else 0):\n",
    "                    # cnt[ri]=i \n",
    "                    ri+=1 \n",
    "                rk2[i1]=ri\n",
    "                # print(i1,ri)\n",
    "            # cnt[ri]=n \n",
    "            rk,rk2=rk2,rk\n",
    "            k<<=1\n",
    "        t=0\n",
    "        ans=\"\"\n",
    "        for i in range(n):\n",
    "            rk[idx[i]]=i \n",
    "        for i in range(n):\n",
    "            if rk[i]==0:\n",
    "                continue \n",
    "            if t>0:\n",
    "                t-=1\n",
    "            j=idx[rk[i]-1]\n",
    "            # if s[i]=='h':\n",
    "            #     print(s[i:i+5],s[j:j+5])\n",
    "            while j+t<n and i+t<n and s[i+t]==s[j+t]:\n",
    "                t+=1\n",
    "            if t>len(ans):\n",
    "                ans=s[i:i+t]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDupSubstring(self, s: str) -> str:\n",
    "        mod = 10**5 + 7\n",
    "        def dfs(n):\n",
    "            begin = 0\n",
    "            for i in range(n):\n",
    "                begin = (begin * 26 + ord(s[i]) - 97) % mod\n",
    "            m = 26 ** (n - 1) % mod \n",
    "            cache = {begin:0}\n",
    "            for i in range(n, l):\n",
    "                begin = ((begin - (ord(s[i - n]) - 97) * m) * 26 + ord(s[i]) - 97) % mod\n",
    "                if begin in cache:\n",
    "                    str_ = s[i + 1 - n : i + 1]\n",
    "                    lis = cache[begin]\n",
    "                    if type(lis) == int:\n",
    "                        ns = s[lis:lis+n]\n",
    "                        if ns == str_:\n",
    "                            return str_\n",
    "                        cache[begin] = [str_,ns]\n",
    "                    else:\n",
    "                        if str_ in lis:\n",
    "                            return str_\n",
    "                        cache[begin].append(str_)\n",
    "                else:\n",
    "                    cache[begin] = i + 1 - n\n",
    "            return \"\"\n",
    "        l = len(s)\n",
    "        left, right, res = 0, l - 1, \"\"\n",
    "        while left < right:\n",
    "            mid = (left + right + 1) // 2\n",
    "            ans = dfs(mid)\n",
    "            if ans:\n",
    "                res = ans\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import islice\n",
    "\n",
    "class Solution:\n",
    "    def longestDupSubstring(self, S: str) -> str:\n",
    "        rank_to_index = list(range(len(S)))\n",
    "        index_to_rank = [0] * len(S)\n",
    "        index_to_rank_list = [index_to_rank]\n",
    "        for i, a in enumerate(S):\n",
    "            index_to_rank[i] = ord(a)\n",
    "        rank_to_index.sort(key=lambda x: index_to_rank[x])\n",
    "        l = 1\n",
    "        def next_rank(x):\n",
    "            return (index_to_rank[x], index_to_rank[x + l] if x + l < len(S) else -1)\n",
    "        while l < len(S):\n",
    "            rank_to_index.sort(key=next_rank)\n",
    "            r = 0\n",
    "            index_to_rank2 = [0] * len(index_to_rank)\n",
    "            index_to_rank2[rank_to_index[0]] = r\n",
    "            for last_ind, ind in zip(rank_to_index, islice(rank_to_index, 1, None)):\n",
    "                if next_rank(ind) != next_rank(last_ind):\n",
    "                    r += 1\n",
    "                index_to_rank2[ind] = r\n",
    "            index_to_rank = index_to_rank2\n",
    "            index_to_rank_list.append(index_to_rank)\n",
    "            l += l\n",
    "            if r == len(index_to_rank):\n",
    "                break\n",
    "        ans = 0\n",
    "        pos = 0\n",
    "        for i, j in zip(rank_to_index, islice(rank_to_index, 1, None)):\n",
    "            c = 0\n",
    "            i2 = i\n",
    "            j2 = j\n",
    "            for k in range(len(index_to_rank_list) - 1, -1, -1):\n",
    "                ir = index_to_rank_list[k]\n",
    "                if ir[i2] == ir[j2]:\n",
    "                    c += (1 << k)\n",
    "                    i2 += (1 << k)\n",
    "                    j2 += (1 << k)\n",
    "                    if i2 >= len(S) or j2 >= len(S):\n",
    "                        break\n",
    "            if c > ans:\n",
    "                ans = c\n",
    "                pos = i\n",
    "        return S[pos: pos + ans]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDupSubstring(self, s: str) -> str:\n",
    "        base = 27\n",
    "        mod = int(3e20)\n",
    "        pow27 = [0 for _ in range(len(s))]\n",
    "        pow27[0] = 1\n",
    "        for i in range(1, len(s)):\n",
    "            pow27[i] = pow27[i - 1] * base % mod\n",
    "        prefix_hash = [0 for _ in range(len(s))]\n",
    "        prefix_hash[0] = ord(s[0]) - 96\n",
    "        for i in range(1, len(s)):\n",
    "            prefix_hash[i] = (prefix_hash[i - 1] * 27 % mod + ord(s[i]) - 96) % mod\n",
    "\n",
    "        def search(l, r):\n",
    "            m = (l + r + 1) // 2\n",
    "            h = prefix_hash[m-1]\n",
    "            search_set = set()\n",
    "            search_set.add(h)\n",
    "            flag = False\n",
    "            for i in range(m, len(s)):\n",
    "                h = ((h - (ord(s[i - m]) - 96) * pow27[m - 1]) * 27 + (ord(s[i]) - 96) * pow27[0]) % mod\n",
    "                if h in search_set:\n",
    "                    flag = True\n",
    "                    break\n",
    "                else:\n",
    "                    search_set.add(h)\n",
    "            if flag is True:\n",
    "                if l == m:\n",
    "                    return s[i - m + 1:i + 1]\n",
    "                else:\n",
    "                    return search(m, r)\n",
    "            else:\n",
    "                return search(l, m - 1)\n",
    "        return search(0,len(s))\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDupSubstring(self, s: str) -> str:\n",
    "        global f\n",
    "        f = [0] * (len(s)*2+50)\n",
    "        sam = SAM(s)\n",
    "        \n",
    "\n",
    "        def dfs(x):\n",
    "            for j in sam.g[x]:\n",
    "                dfs(j)\n",
    "                f[x] += f[j]\n",
    "\n",
    "        dfs(0)\n",
    "        #state = list(range(1,sam.sz))\n",
    "        #state.sort(key = lambda x:sam.st[x].length,reverse = True)\n",
    "        #for x in state:\n",
    "        #    if f[x] > 1:\n",
    "        #        pos = sam.st[x].pos\n",
    "        #        length = sam.st[x].length\n",
    "        #        return s[pos+1-length:pos+1]\n",
    "        ans = \"\"\n",
    "        al = 0\n",
    "        for x in range(1,sam.sz):\n",
    "            if f[x] > 1 and sam.st[x].length > al:\n",
    "                pos = sam.st[x].pos\n",
    "                length = sam.st[x].length\n",
    "                ans =  s[pos+1-length:pos+1]\n",
    "                al = length\n",
    "\n",
    "\n",
    "\n",
    "        return ans\n",
    "\n",
    "        \n",
    "\n",
    "f = [0] * (60000+50)\n",
    "from typing import OrderedDict, List\n",
    "from copy import deepcopy\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "class State:\n",
    "    def __init__(self, length=None, link=None, trans={}, pos=-1):\n",
    "        self.length = length\n",
    "        self.link = link\n",
    "        self.trans = trans\n",
    "        self.pos = pos\n",
    "\n",
    "    def __str__(self):\n",
    "        return f'{str(self.trans)} {self.pos}'\n",
    "\n",
    "\n",
    "\n",
    "class SAM:\n",
    "    def __init__(self, s=\"\"):\n",
    "        self.last = 0\n",
    "        self.sz = 1\n",
    "        self.st = OrderedDict({0: State(0, -1, OrderedDict(), -1)})\n",
    "        self.g = defaultdict(list)\n",
    "        self(s)\n",
    "\n",
    "    def _extend(self, c, pos):\n",
    "        cur = self.sz\n",
    "        self.st[cur] = State(None, None, OrderedDict(), pos)\n",
    "        f[cur] = 1\n",
    "        self.st[cur].length = self.st[self.last].length + 1\n",
    "        p = self.last\n",
    "        while p > -1 and self.st[p].trans.get(c) is None:\n",
    "            self.st[p].trans[c] = cur\n",
    "            p = self.st[p].link\n",
    "        if p == -1:\n",
    "            self.st[cur].link = 0\n",
    "        else:\n",
    "            q = self.st[p].trans[c]\n",
    "            if self.st[p].length + 1 == self.st[q].length:\n",
    "                self.st[cur].link = q\n",
    "            else:\n",
    "                self.sz += 1\n",
    "                self.st[self.sz] = State(\n",
    "                    self.st[p].length + 1,\n",
    "                    self.st[q].link,\n",
    "                    deepcopy(self.st[q].trans),\n",
    "                    self.st[q].pos,\n",
    "                )\n",
    "\n",
    "                while p > -1 and self.st[p].trans.get(c) == q:\n",
    "\n",
    "                    self.st[p].trans[c] = self.sz\n",
    "                    p = self.st[p].link\n",
    "                self.st[q].link = self.st[cur].link = self.sz\n",
    "        self.sz += 1\n",
    "        self.last = cur\n",
    "\n",
    "    def __call__(self, s):\n",
    "        for i, c in enumerate(s):\n",
    "            self._extend(c, i)\n",
    "        for i in range(self.sz):\n",
    "            self.g[self.st[i].link].append(i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDupSubstring(self, s: str) -> str:\n",
    "        if len(s) == 0 or len(s) == 1:\n",
    "            return \"\"\n",
    "        \n",
    "        def calc_sum(s):\n",
    "            base= 0\n",
    "            for c in s:\n",
    "                base*=26 \n",
    "                base+=(ord(c)-ord('a')) \n",
    "            return base\n",
    "\n",
    "        def update(checksum, a,b,head):\n",
    "            checksum*=26\n",
    "            checksum -=(ord(a)-ord('a'))*head \n",
    "            checksum += ord(b)-ord('a')\n",
    "            return checksum \n",
    "        def check(s,n):\n",
    "            ss = set()\n",
    "            base_str = s[:n]\n",
    "            start_pos = 0\n",
    "            end_pos = n-1 \n",
    "            checksum = calc_sum(base_str)\n",
    "            head = 1 \n",
    "            for idx in range(n):\n",
    "                head*=26\n",
    "            ss.add(checksum)\n",
    "            for idx in range(1, len(s)-n+1,1):\n",
    "                checksum = update(checksum,s[start_pos],s[end_pos+1],head)\n",
    "                if checksum in ss:\n",
    "                    return True, s[start_pos+1:end_pos+2]\n",
    "                ss.add(checksum)\n",
    "                start_pos+=1\n",
    "                end_pos+=1\n",
    "            return False,False\n",
    "        left = 1\n",
    "        right = len(s)-1\n",
    "        a,b = check(s,1)\n",
    "        if not a:\n",
    "            return ''\n",
    "        a,b = check(s, len(s)-1)\n",
    "        if a :\n",
    "            return s[1:]\n",
    "\n",
    "        while left <= right:\n",
    "            mid = (left+right)//2\n",
    "            a,b = check(s,mid)\n",
    "            if a:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return check(s,left-1)[1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDupSubstring(self, s: str) -> str:\n",
    "        h = 26\n",
    "        arr = [ord(c)-ord('a') for c in s]\n",
    "        def check(l):\n",
    "            p = h**(l-1)\n",
    "            cur = 0\n",
    "            for i in range(l):\n",
    "                cur = (cur*h+arr[i])\n",
    "            seen = {cur}\n",
    "            for i in range(1, len(arr)-l+1):\n",
    "                cur = ((cur - arr[i-1]*p)*h+arr[i+l-1])\n",
    "                if cur in seen:\n",
    "                    return i\n",
    "                seen.add(cur)\n",
    "            return -1\n",
    "\n",
    "        l, r, pos, ml = 1, len(s)-1, -1, -1\n",
    "        while l<=r:\n",
    "            mid = (l + r) //2\n",
    "            t = check(mid)\n",
    "            if t != -1: pos, l, ml = t, mid + 1, mid\n",
    "            else: r = mid - 1\n",
    "\n",
    "        if pos == -1: return ''\n",
    "        else: return s[pos:pos+ml]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def longestDupSubstring(self, s: str) -> str:\n",
    "        n, BASE = len(s), 26\n",
    "        cov = lambda x: ord(x) - ord('a')\n",
    "        ans = ''\n",
    "\n",
    "        def check(ln):\n",
    "            nonlocal ans\n",
    "            base = 0\n",
    "            for i in range(ln):\n",
    "                base = base * BASE + cov(s[i])\n",
    "            vis = set([base])\n",
    "            r = pow(BASE, ln - 1)\n",
    "            for i in range(1, n - ln + 1):\n",
    "                base = (base - r * cov(s[i - 1])) * BASE + cov(s[i + ln - 1])\n",
    "                if base in vis:\n",
    "                    ans = s[i:i + ln]\n",
    "                    return True\n",
    "                vis.add(base)\n",
    "            return False\n",
    "\n",
    "        l, r = 1, n - 1\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            if check(mid):\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDupSubstring(self, s: str) -> str:\n",
    "        def check(arr, m, a1, a2):\n",
    "            n = len(arr)\n",
    "            tr1, tr2 = pow(a1, m), pow(a2, m)\n",
    "            # 初始化\n",
    "            h1, h2 = 0, 0\n",
    "            for i in range(m):\n",
    "                h1 = h1 * a1 + arr[i]\n",
    "                # h2 = h2 * a2 + arr[i]\n",
    "            seen = {(h1, h2)}\n",
    "            for start in range(1, n - m + 1):\n",
    "                h1 = h1 * a1 - arr[start-1] * tr1 + arr[start+m-1]\n",
    "                # h2 = h2 * a2 - arr[start-1] * tr2 + arr[start+m-1]\n",
    "                if (h1, h2) in seen:\n",
    "                    return start\n",
    "                seen.add((h1, h2))\n",
    "            return -1\n",
    "        \n",
    "        n = len(s)\n",
    "        ar = [ord(ele) - ord('a') for ele in s]\n",
    "        a1 = 26\n",
    "        a2 = 29\n",
    "\n",
    "        l, r = 1, n - 1\n",
    "        start, length = -1, 0\n",
    "        while l <= r:\n",
    "            m = l + (r - l) // 2\n",
    "            flag = check(ar, m, a1, a2)\n",
    "            if flag == -1:\n",
    "                r = m - 1\n",
    "            else:\n",
    "                start = flag\n",
    "                length = m\n",
    "                l = m + 1\n",
    "        return s[start:start+length] if start != -1 else ''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# if there exists duplicated substring of length l > 1 in s\r\n",
    "# l - 1 length of it will also be a duplicated substring\r\n",
    "# thus possible to binary search for length\r\n",
    "from bisect import bisect\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def longestDupSubstring(self, s: str) -> str:\r\n",
    "        n = len(s)\r\n",
    "        prm = 31\r\n",
    "        st = -1\r\n",
    "\r\n",
    "        def exists(mid: int) -> bool:\r\n",
    "            nonlocal st\r\n",
    "            h = 0\r\n",
    "            p = prm ** (mid - 1)\r\n",
    "            for i in range(mid):\r\n",
    "                h *= prm\r\n",
    "                h += ord(s[i]) - 97\r\n",
    "            \r\n",
    "            visited = {h}\r\n",
    "            for i in range(mid, n):\r\n",
    "                h -= p * (ord(s[i - mid]) - 97)\r\n",
    "                h *= prm\r\n",
    "                h += ord(s[i]) - 97\r\n",
    "                if h in visited:\r\n",
    "                    st = i - mid + 1\r\n",
    "                    return False\r\n",
    "                visited.add(h)\r\n",
    "            return True\r\n",
    "\r\n",
    "        l = bisect(range(n), False, key=exists) - 1\r\n",
    "        return s[st: st + l]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def check(self, s, length):\n",
    "        # 滚动hash\n",
    "        p_hash = 0\n",
    "        n = len(s)\n",
    "        mod = n * 100\n",
    "        count = set()\n",
    "        BASE = 27\n",
    "        MASK = (1 << length*5) - 1\n",
    "        for i in range(length):\n",
    "            # p_hash = p_hash + (ord(s[i]) - 97) * BASE**(length - i)\n",
    "            p_hash = ((p_hash << 5) | (ord(s[i])-97)) & MASK\n",
    "        count.add(p_hash)\n",
    "        # if length < 5:\n",
    "        #     print(MASK, p_hash)\n",
    "        for i in range(length, n):\n",
    "            # if length < 5:\n",
    "            #     print(p_hash, s[i-length:i])\n",
    "            # p_hash = (p_hash - (ord(s[i-length]) - 97)*BASE**length)*BASE + (ord(s[i])-97)*BASE\n",
    "            p_hash = ((p_hash << 5) | (ord(s[i])-97)) & MASK\n",
    "            if p_hash in count:\n",
    "                return s[i-length+1:i+1]\n",
    "            count.add(p_hash)\n",
    "        return \"\"\n",
    "\n",
    "    def longestDupSubstring(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        left = 1\n",
    "        right = n - 1\n",
    "        ans = ''\n",
    "        while left <= right:\n",
    "            mid = left + right >> 1\n",
    "            # print(mid)\n",
    "            sub = self.check(s, mid)\n",
    "            if sub:\n",
    "                left = mid + 1\n",
    "                ans = sub\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDupSubstring(self, s: str) -> str:\n",
    "        length = len(s)\n",
    "        res = ''\n",
    "        skip = 150  # 步长跨度\n",
    "        step = skip if length > skip else 1  # 步长\n",
    "        i = 0  # 子字符串截取长度\n",
    "        while i < length + 1:\n",
    "            i += step\n",
    "            sets = set()\n",
    "            flag = 0\n",
    "            for j in range(length - i + 1):\n",
    "                tmpStr = s[j:(i + j)]  # 截取子字符串\n",
    "                if tmpStr in sets:  # 判断是否有相同的子字符串\n",
    "                    # print(tmpStr)\n",
    "                    flag = 1\n",
    "                    break\n",
    "                sets.add(tmpStr)\n",
    "            if flag == 1:  # 有相同的子字符串\n",
    "                res = tmpStr\n",
    "            else:  # 没有有相同的子字符串\n",
    "                if step == skip:\n",
    "                    step = 1  # 步长变成1\n",
    "                    i -= skip  # 从上次循环的位置继续\n",
    "                else:\n",
    "                    return res\n",
    "        return ''\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDupSubstring(self, s: str) -> str:\n",
    "        length = len(s)\n",
    "        res = ''\n",
    "        skip = 150  # 步长跨度\n",
    "        step = skip if length > skip else 1  # 步长\n",
    "        i = 0  # 子字符串截取长度\n",
    "        while i < length + 1:\n",
    "            i += step\n",
    "            sets = set()\n",
    "            flag = 0\n",
    "            for j in range(length - i + 1):\n",
    "                tmpStr = s[j:(i + j)]  # 截取子字符串\n",
    "                if tmpStr in sets:  # 判断是否有相同的子字符串\n",
    "                    # print(tmpStr)\n",
    "                    flag = 1\n",
    "                    break\n",
    "                sets.add(tmpStr)\n",
    "            if flag == 1:  # 有相同的子字符串\n",
    "                res = tmpStr\n",
    "            else:  # 没有有相同的子字符串\n",
    "                if step == skip:\n",
    "                    step = 1  # 步长变成1\n",
    "                    i -= skip  # 从上次循环的位置继续\n",
    "                else:\n",
    "                    return res\n",
    "        return ''\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDupSubstring(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        def searchAnySubstring(length):\n",
    "            record = set()\n",
    "            for i in range(n-length+1):\n",
    "                cur = s[i:i+length]\n",
    "                if cur not in record:\n",
    "                    record.add(cur)\n",
    "                else:\n",
    "                    return (True,i)\n",
    "            return (False,'')\n",
    "        l = 1\n",
    "        r = len(s)-1\n",
    "        count = 0\n",
    "        ans = ''\n",
    "        print(searchAnySubstring(1))\n",
    "        while l<=r:\n",
    "            mid = l+(r-l)//2\n",
    "            flag,start= searchAnySubstring(mid)\n",
    "            if flag:\n",
    "                if mid>count:\n",
    "                    count = mid\n",
    "                    ans = s[start:start+mid]\n",
    "                l = mid+1\n",
    "            else:\n",
    "                r = mid-1\n",
    "      \n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDupSubstring(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        def check(s: str, l: int) -> str:\n",
    "            se = set()\n",
    "            for i in range(0,n-l+1):\n",
    "                if s[i:i+l] in se:\n",
    "                    return s[i:i+l]\n",
    "                else:\n",
    "                    se.add(s[i:i+l])\n",
    "            return ''\n",
    "        solution = ''\n",
    "        i,j = 1,n-1\n",
    "        while i <= j:\n",
    "            mid = i + (j - i + 1) // 2\n",
    "            x = check(s,mid)\n",
    "            if x != '':\n",
    "                i = mid + 1\n",
    "                solution = x\n",
    "            else:\n",
    "                j = mid - 1\n",
    "        return solution\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
